﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Threading;

namespace Pixysoft.Collections
{
    class DoubleLinkedList<T> : IEnumerable<T>, IEnumerable
    {
        object m_syncRoot = new object();
        public LinkItem HeadLink = null;
        public LinkItem TailLink = null;
        int m_count = 0;


        /// <summary>
        /// Prepend the specified value to the head of the list
        /// </summary>
        /// <param name="value">Value to prepend to the list (not a LinkItem)</param>
        /// <returns>The LinkItem which points to this new value</returns>
        public LinkItem Prepend(string key, T value)
        {
            LinkItem newItem = new LinkItem(HeadLink, null, key, value);

            if (HeadLink != null)
                HeadLink.Previous = newItem;

            if (TailLink == null)
                TailLink = newItem;

            HeadLink = newItem;

            // Increment the count
            Interlocked.Increment(ref m_count);

            return newItem;
        }
        /// <summary>
        /// Append the specified value to the tail of the list (not a LinkItem)
        /// </summary>
        /// <param name="value">The value to append to the list</param>
        /// <returns>The new LinkItem which points to the value</returns>
        public LinkItem Append(string key, T value)
        {
            // Append this item to the tail
            if (TailLink != null)
            {
                TailLink = new LinkItem(null, TailLink, key, value);
                TailLink.Previous.Next = TailLink;
            }

            if (HeadLink == null)
                HeadLink = TailLink;

            // Increment the count
            Interlocked.Increment(ref m_count);

            return TailLink;
        }
        /// <summary>
        /// Remove the specified link from the list
        /// </summary>
        /// <param name="item">Item to remove </param>
        public void RemoveLink(LinkItem item)
        {
            // Check the arguments
            if (item == null)
                return;

            LinkItem next = item.Next;
            LinkItem prev = item.Previous;

            if (HeadLink == item)
                HeadLink = next;
            if (TailLink == item)
                TailLink = prev;

            if (prev != null)
                prev.Next = next;
            if (next != null)
                next.Previous = prev;

            // Decrement the count
            Interlocked.Decrement(ref m_count);
        }
        /// <summary>
        /// Move the specified LinkItem to the head of the list
        /// </summary>
        /// <param name="item">The existing LinkItem in the list</param>
        public void MoveToHead(LinkItem item)
        {
            if (item == null)
                return;

            if (item != HeadLink)
            {
                LinkItem prev = item.Previous;
                LinkItem next = item.Next;

                if (prev != null)
                    prev.Next = next;
                if (next != null)
                    next.Previous = prev;

                if (TailLink == item)
                    TailLink = prev;

                if (HeadLink != null)
                    HeadLink.Previous = item;

                item.Next = HeadLink;
                item.Previous = null;
                HeadLink = item;
            }
        }





        public bool IsReadOnly
        {
            get
            {
                // TODO:  Add DoubleLinkedList.IsReadOnly getter implementation
                return false;
            }
        }

        public void RemoveAt(int index)
        {
            int i = 0;
            LinkItem current = HeadLink;

            // Skip past existing items
            for (i = 0, current = HeadLink; current != null && i < index; i++, current = current.Next) ;

            if (i == index && current != null)
            {
                LinkItem prev = current.Previous;
                LinkItem next = current.Next;

                if (current == HeadLink)
                {
                    HeadLink = next;
                }
                else if (prev != null)
                {
                    prev.Next = next;
                }

                if (TailLink == current)
                {
                    TailLink = prev;
                }
                else if (next != null)
                {
                    next.Previous = prev;
                }

                // Decrement the count
                Interlocked.Decrement(ref m_count);
            }
        }

        public void Clear()
        {
            HeadLink = null;
            TailLink = null;
        }

        public bool IsFixedSize
        {
            get
            {
                return false;
            }
        }

        public bool IsSynchronized
        {
            get
            {
                // TODO:  Add DoubleLinkedList.IsSynchronized getter implementation
                return false;
            }
        }

        public int Count
        {
            get
            {
                return m_count;
            }
        }

        public object SyncRoot
        {
            get
            {
                return m_syncRoot;
            }
        }


        public int IndexOf(T item)
        {
            LinkItem current = HeadLink;
            int index = -1;

            // Skip past existing items
            for (index = 0, current = HeadLink;
                current != null && !current.Item.Equals(item);
                index++, current = current.Next) ;

            if (current != null)
            {
                return index;
            }

            return -1;
        }

        public void Insert(int index, string key, T item)
        {
            int i = 0;
            LinkItem current = HeadLink;

            // Skip past existing items
            for (i = 0, current = HeadLink; current != null && i < index; i++, current = current.Next) ;

            if (i == index && current != null)
            {
                // Create the next link item
                LinkItem newItem = new LinkItem(current, current.Previous, key, item);

                current.Previous.Next = newItem;
                current.Previous = newItem;

                if (HeadLink == current)
                    HeadLink = newItem;

                // Adjust the count
                Interlocked.Increment(ref m_count);
            }
            else if (current == null)
            {
                Add(key, item);
            }
        }

        public T this[int index]
        {
            get
            {
                int i = 0;
                LinkItem current = HeadLink;
                T item = default(T);

                // Skip to the index
                for (i = 0, current = HeadLink; current != null && i < index; i++, current = current.Next) ;

                if (i == index && current != null)
                {
                    item = current.Item;
                }

                return item;
            }
            set
            {
                int i = 0;
                LinkItem current = HeadLink;

                // Skip past existing items
                for (i = 0, current = HeadLink; current != null && i < index; i++, current = current.Next) ;

                if (i == index && current != null)
                {
                    current.Item = value;
                }
            }
        }



        public void Add(string key, T item)
        {
            // Append this item to the tail
            TailLink = new LinkItem(null, TailLink, key, item);

            if (TailLink.Previous != null)
            {
                TailLink.Previous.Next = TailLink;
            }

            if (HeadLink == null)
                HeadLink = TailLink;

            // Adjust the count
            Interlocked.Increment(ref m_count);

        }

        public bool Contains(T item)
        {
            LinkItem current = HeadLink;
            bool hasItem = false;

            // Skip past existing items
            for (current = HeadLink; current != null && !current.Item.Equals(item); current = current.Next) ;

            if (current != null)
            {
                hasItem = true;
            }

            return hasItem;
        }

        public void CopyTo(T[] array, int index)
        {
            int i = 0;
            LinkItem current = null;

            for (i = 0, current = HeadLink;
                current != null && (i + index) < array.Length;
                i++, current = current.Next)
            {
                array.SetValue(current.Item, index + i);
            }
        }

        public bool Remove(T item)
        {
            LinkItem current;

            // Skip past existing items
            for (current = HeadLink; current != null && !current.Item.Equals(item); current = current.Next) ;

            if (current != null)
            {
                LinkItem prev = current.Previous;
                LinkItem next = current.Next;

                if (current == HeadLink)
                {
                    HeadLink = next;
                }
                else if (prev != null)
                {
                    prev.Next = next;
                }

                if (current == TailLink)
                {
                    TailLink = prev;
                }
                else if (next != null)
                {
                    next.Previous = prev;
                }

                // Adjust the count
                Interlocked.Decrement(ref m_count);

                return false;
            }

            return false;
        }


        public IEnumerator<T> GetEnumerator()
        {
            return new EnumLinkList(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new EnumLinkList(this);
        }

        /// <summary>
        /// Public class to enumerate the items in the list
        /// </summary>
        class EnumLinkList : IEnumerator<T>
        {
            DoubleLinkedList<T> m_list = null;

            LinkItem m_current = null;

            public EnumLinkList(DoubleLinkedList<T> list)
            {
                m_list = list;
            }

            public T Current
            {
                get
                {
                    return m_current.Item;
                }
            }

            public bool MoveNext()
            {
                bool result = false;

                if (m_current == null)
                {
                    // There are no items in the list
                    if (m_list.HeadLink == null)
                        return false;

                    m_current = m_list.HeadLink;
                    result = true;
                }
                else if (m_current.Next == null)
                {
                    m_current = null;
                    result = false;
                }
                else
                {
                    m_current = m_current.Next;
                    result = true;
                }

                return result;
            }

            public void Reset()
            {
                m_current = null;
            }

            public void Dispose()
            {
                Reset();
            }

            object IEnumerator.Current
            {
                get { return Current; }
            }
        }

        public class LinkItem
        {
            /// <summary>
            /// Next item in the list
            /// </summary>
            private LinkItem next;
            /// <summary>
            /// Previous item in the list
            /// </summary>
            private LinkItem previous;
            /// <summary>
            /// 键值
            /// </summary>
            private string key;
            /// <summary>
            /// Current item that this node points to (ie the value)
            /// </summary>
            private T item;

            /// <summary>
            /// Build a new LinkItem pointing to the next, previous and current value
            /// </summary>
            /// <param name="next">The next LinkItem in the list</param>
            /// <param name="previous">The previous LinkItem in the list</param>
            /// <param name="item">The current value that this item points to</param>
            public LinkItem(LinkItem next, LinkItem previous, string key, T item)
            {
                Next = next;
                Previous = previous;
                Key = key;
                Item = item;
            }

            /// <summary>
            /// Next item in the list
            /// </summary>
            public LinkItem Next
            {
                get { return next; }
                set { next = value; }
            }

            /// <summary>
            /// Previous item in the list
            /// </summary>
            public LinkItem Previous
            {
                get { return previous; }
                set { previous = value; }
            }

            /// <summary>
            /// 键值
            /// </summary>
            public string Key
            {
                get { return key; }
                set { key = value; }
            }

            /// <summary>
            /// Current item that this node points to (ie the value)
            /// </summary>
            public T Item
            {
                get { return item; }
                set { item = value; }
            }

            public override string ToString()
            {
                if (Item != null)
                    return Item.ToString();
                else
                    return "null";
            }

        }
    }
}
